package com.lzq.leetcode.hoot100;

import java.util.Deque;
import java.util.LinkedList;

public class s394 {
    public String decodeString(String s) {
        Deque<String> stack = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        // 解析
        for (int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            if (c == '[') {
                // 入栈
                if (!sb.isEmpty()) {
                    stack.addFirst(sb.toString());
                    sb.delete(0, sb.length());
                }
                stack.addFirst("[");
                sb.delete(0, sb.length());
            } else if (c == ']') {
                // 出栈直到找到'['
                stack.addFirst(sb.toString());
                sb.delete(0, sb.length());
                while (!stack.getFirst().equals("[")) {
                    sb.insert(0, stack.pollFirst());
                }
                // 乘倍数
                stack.pollFirst();
                StringBuilder newApp = new StringBuilder();
                int num = Integer.parseInt(stack.pollFirst());
                for (int j=0; j<num; j++) {
                    newApp.append(sb);
                }
                // 重新入栈
                stack.addFirst(newApp.toString());
                sb.delete(0, sb.length());
            } else {
                // 数字
                if (isNum(s, i)) {
                    if (!sb.isEmpty() && !isNum(sb.charAt(sb.length() - 1))) {
                        // 入栈, 清空
                        stack.addFirst(sb.toString());
                        sb.delete(0, sb.length());
                    }
                    sb.append(c);
                } else {
                    // 字符
                    if (!sb.isEmpty() && isNum(sb.charAt(sb.length() - 1))) {
                        // 入栈, 清空
                        stack.addFirst(sb.toString());
                        sb.delete(0, sb.length());
                    }
                    sb.append(c);
                }
            }
        }
        StringBuilder builder = new StringBuilder();
        // 转化为String
        while (!stack.isEmpty()) {
            builder.append(stack.pollLast());
        }
        builder.append(sb);

        return builder.toString();
    }

    private boolean isNum(String str, int i) {
        return isNum(str.charAt(i));
    }

    private boolean isNum(char c) {
        return c >= '0' && c <= '9';
    }

    public static void main(String[] args) {
        System.out.println(new s394().decodeString("3[a2[c]]"));
    }
}
